#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <map>
using namespace std;

struct Node {
	int t;
	int val;
	Node(int a, int b) :t(a), val(b) {}
};

int main()
{
	string type; cin >> type; //cout << type << endl;
	bool DUN = 0, GN = 0; // 有向无向、带不带权
	if (type == "DG")  DUN = 1, GN = 0;
	if (type == "DN")  DUN = 1, GN = 1;
	if (type == "UDG") DUN = 0, GN = 0;
	if (type == "UDN") DUN = 0, GN = 1;
	int n; cin >> n; vector<string> nodes(n);
	map<string, int> ntoi; // node to index
	for (int i = 0; i < n; i++) {
		cin >> nodes[i]; if (i) cout << ' '; cout << nodes[i];
		ntoi[nodes[i]] = i;
	}	cout << endl;
	string flag("0"); vector<list<Node>> graph(n);
	int k; cin >> k; //cout << k << endl;
	vector<vector<int>> path(k, vector<int>(2 + GN)); // 带权的话 给权值留个位置
	for (int i = 0; i < k; i++) cin >> path[i][0] >> path[i][1];
	if (GN) for (int i = 0; i < k; i++)  cin >> path[i][2];
	for (auto& v : path) {
		graph[v[0]].push_front(Node(v[1], (GN ? v[2] : 0)));
		if (!DUN) graph[v[1]].push_front(Node(v[0], (GN ? v[2] : 0)));
	}
	for (int i = 0; i < n; i++) {
		if (i)cout << endl;
		cout << nodes[i];
		for (auto e : graph[i]) {
			cout << "->" << e.t;
			if(GN) cout << "(" << e.val << ")";
		}
		cout << "->nullptr";
	}

	cout << "\n\n";

	int tgt; cin >> tgt;
	queue<int> q; q.push(tgt);
	vector<bool> visited(n);
	visited[tgt] = 1;
	while (q.size()) {
		int cur = q.front(); q.pop();
		if (cur != tgt) cout << "->";
		cout << nodes[cur];
		for (auto& e : graph[cur]) {
			if (visited[e.t]) continue;
			visited[e.t] = 1;
			q.push(e.t);
		}
	}

	return 0;
}